import java.util.*;

//树的样子为：
//       1
//   2       3
// 4  5     6  7


public class treeTraverse {

    //节点的值
    private int arr[] = {1,2,3,4,5,6,7};
    //二叉树链表
    private static List<Node> nodelist = null;

    //定义二叉树类
    private static class Node{
        Node left;
        Node right;
        int data;
        Node(int newdata){
            left = null;
            right = null;
            data = newdata;
        }
    }

    //构建二叉树
    public void createTree(){
        nodelist = new LinkedList<Node>();
        for(int i = 0; i < arr.length; i++){
            nodelist.add(new Node(arr[i]));
        }
        for(int parentIndex = 0; parentIndex < arr.length/2-1 ; parentIndex++){
            nodelist.get(parentIndex).left = nodelist.get(parentIndex*2+1);
            nodelist.get(parentIndex).right = nodelist.get(parentIndex*2+2);
        }
        int lastParentIndex = arr.length/2-1;
        nodelist.get(lastParentIndex).left = nodelist.get(lastParentIndex*2+1);
        if(arr.length%2 == 1){
            nodelist.get(lastParentIndex).right = nodelist.get(lastParentIndex*2+2);
        }
    }

    //前序遍历
    // 将根节点放入栈，然后出栈，如果节点有子节点，则按照先右子节点，再左子节点将其入栈，这样下一轮就是左节点先出栈，实现“根左右”的顺序遍历
    public static List<Integer> preOrder(Node node){
        Stack<Node> tmp1 = new Stack<>();
        List<Integer> res1 = new ArrayList<>();
        tmp1.add(node);
        while(!tmp1.isEmpty()){
            Node index = tmp1.pop();
            res1.add(index.data);
            if(index.right != null) {
                tmp1.add(index.right);
            }
            if(index.left != null){
                tmp1.add(index.left);
            }
        }
        return res1;
    }

    //中序遍历
    //当前节点不为空或者栈不为空时进入循环，如果当前节点不为空，则将其入栈，然后开始走它的左子树，一直走，直到发现左子树走完，不再有左节点能入栈，则出栈（出栈的节点就是这个左子树的最后一个左子节点）
    //对于出栈的节点，使index指向它的右子节点，如果右子节点不为空，将其入栈；如果为空，则再次出栈，此时出栈的节点是上一层的根节点，然后再处理根节点的右子节点，则形成”左根右“的顺序
    public static List<Integer> inOrder(Node node){
        Stack<Node> tmp2 = new Stack<>();
        List<Integer> res2 = new ArrayList<>();
        Node index = node;
        while(index != null || !tmp2.isEmpty()){
            while(index != null){
                tmp2.add(index);
                index = index.left;
            }
            index = tmp2.pop();
            res2.add(index.data);
            index = index.right;
        }
        return res2;
    }

    //后序遍历
    //与前序遍历类似，先将根节点放入栈再出栈，然后对于出栈的节点，按照先左子节点，再右子节点的顺序入栈，这样下一层就先处理右子节点
    //形成“根右左”的顺序，再将答案逆序即可，为“左右根”的顺序
    public static List<Integer> postOrder(Node node){
        Stack<Node> tmp3 = new Stack<>();
        List<Integer> res3 = new ArrayList<>();
        tmp3.add(node);
        while(!tmp3.isEmpty()){
            Node index = tmp3.pop();
            res3.add(index.data);
            if(index.left != null){
                tmp3.add(index.left);
            }
            if(index.right != null){
                tmp3.add(index.right);
            }
        }
        return res3;
    }

    public static void main(String[] args) {
        //初始化二叉树
        treeTraverse binTree = new treeTraverse();
        binTree.createTree();
        //二叉树根节点即为上面创建的二叉树链表的头结点
        Node root = nodelist.get(0);

        //前序遍历：根左右
        System.out.print("前序遍历：");
        List<Integer> res1 = preOrder(root);
        for(Integer a : res1){
            System.out.print(a);
        }

        //中序遍历：左根右
        System.out.print("中序遍历：");
        List<Integer> res2 = inOrder(root);
        for(Integer a : res2){
            System.out.print(a);
        }

        //后序遍历：左右根
        System.out.print("后序遍历：");
        List<Integer> res3 = postOrder(root);
        Collections.reverse(res3);
        for(Integer a : res3){
            System.out.print(a);
        }
    }

}
